#include <bits/stdc++.h>

using namespace std;

// 去除重复字母保证剩余字符串的字典序最小
// 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次
// 需保证 返回结果的字典序最小
// 要求不能打乱其他字符的相对位置
// 测试链接 : https://leetcode.cn/problems/remove-duplicate-letters/

class Solution 
{
private:
    static const int MAXN = 26;
    // 每种字符词频
    int cnt[MAXN];
    // 单调栈
    char st[MAXN];
    // 每种字符目前有没有进栈
    bool enter[MAXN];
    int r;

public:
    string removeDuplicateLetters(string s) 
    {
        for(char ch : s) ++cnt[ch - 'a'];

        for(char cur : s)
        {
            if(!enter[cur - 'a'])
            {
                while(r > 0 && st[r - 1] > cur && cnt[st[r - 1] - 'a'] > 0)
                {
                    enter[st[r - 1] - 'a'] = false;
                    --r;
                }
                st[r++] = cur;
                enter[cur - 'a'] = true;
            }
            --cnt[cur - 'a'];
        }
        return string(st, st + r);
    }
};


class Solution 
{
public:
    string removeDuplicateLetters(string s) 
    {
        int cnt[26]{};
        for(char ch : s) ++cnt[ch - 'a'];

        string ret; // 直接使用 string 作为单调栈
        bool visited[26]{};
        for(char ch : s)
        {
            --cnt[ch - 'a'];
            if(visited[ch - 'a']) continue;
            while(!ret.empty() && ch < ret.back() && cnt[ret.back() - 'a'] > 0)
            {
                visited[ret.back() - 'a'] = false;
                ret.pop_back();
            }
            ret += ch;
            visited[ch - 'a'] = true;
        }

        return ret;
    }
};